package training;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_6_17_Training {
    //统计恰好有 K 个相等相邻元素的数组数目
    private final int MOD = (int) 1e9 + 7;

    public int countGoodArrays(int n, int m, int k) {
        return (int) (C(n - 1, k) * m % MOD * pow(m - 1, n - 1 - k) % MOD);
    }

    public long pow(long x, long n) {
        long ans = 1;
        while (n > 0) {
            if ((n & 1) == 1)
                ans = (ans * x) % MOD;
            n >>= 1;
            x = x * x % MOD;
        }
        return ans;
    }

    public long C(int n, int k) {
        long x = 1, y = 1;
        for (int i = n; i > n - k; i--) {
            x = x * i % MOD;
        }
        for (int i = k; i > 0; i--) {
            y = y * i % MOD;
        }
        return comb(x, y);
    }

    public long comb(long a, long b) {
        return a * pow(b, MOD - 2) % MOD;
    }
}
